<?php
/**
 * User: LRZ
 * Date: 2020/3/2
 * Time: 18:19
 */

/**
 *  459.重复的子字符串
 *
 *  标签：字符串
 *
 *  给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
 *
 *  示例 1:
 *      输入: "abab"
 *      输出: True
 *      解释: 可由子字符串 "ab" 重复两次构成。
 *
 *  示例 2:
 *      输入: "aba"
 *      输出: False
 *
 *  示例 3:
 *      输入: "abcabcabcabc"
 *      输出: True
 *      解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/repeated-substring-pattern
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$s   = 'aa';
$res = repeatedSubstringPattern($s);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function repeatedSubstringPattern($s)
{
    # 假设$s是由$a重复N次得到
    # 则$S = $s+$s是由$a重复2N次得到
    # 去掉$S的头和尾，则破坏了这两处的子串
    # 如果剩余的字符串还存在$s，就说明这是重复的子字符串
    $S = $s . $s;
    $S = substr($S, 1, -1);
    return strpos($S, $s) !== false;
}